Example 2 Clustering Geometric Objects¶

In this example we will look at a few of the tools provided by the clifford package for (4,1) conformal geometric algebra (CGA) and see how we can use them in a practical setting to cluster geometric objects via the simple K-means clustering algorithm provided in clifford.tools

As before the first step in using the package for CGA is to generate and import the algebra:

[1]:

from clifford.g3c import *
print('e1*e1 ', e1*e1)
print('e2*e2 ', e2*e2)
print('e3*e3 ', e3*e3)
print('e4*e4 ', e4*e4)
print('e5*e5 ', e5*e5)

e1*e1  1.0
e2*e2  1.0
e3*e3  1.0
e4*e4  1.0
e5*e5  -1.0

The tools submodule of the clifford package contains a wide array of algorithms and tools that can be useful for manipulating objects in CGA. In this case we will be generating a large number of objects and then segmenting them into clusters.

We first need an algorithm for generating a cluster of objects in space. We will construct this cluster by generating a random object and then repeatedly disturbing this object by some small fixed amount and storing the result:

[2]:

from clifford.tools.g3c import *
import numpy as np

def generate_random_object_cluster(n_objects, object_generator, max_cluster_trans=1.0, max_cluster_rot=np.pi/8):
    """ Creates a cluster of random objects """
    ref_obj = object_generator()
    cluster_objects = []
    for i in range(n_objects):
        r = random_rotation_translation_rotor(maximum_translation=max_cluster_trans, maximum_angle=max_cluster_rot)
        new_obj = apply_rotor(ref_obj, r)
        cluster_objects.append(new_obj)
    return cluster_objects

We can use this function to create a cluster and then we can visualise this cluster with GAOnline using the built in tools in clifford.

[3]:

from clifford.tools.g3c.GAOnline import *
clustered_circles = generate_random_object_cluster(10, random_circle)
sc = GAScene()
for c in clustered_circles:
    sc.add_circle(c,'rgb(255,0,0)')
print(sc)

DrawCircle((0.08725^e123) - (2.04208^e124) - (2.06774^e125) + (4.00024^e134) + (4.04713^e135) + (0.07887^e145) - (0.37904^e234) - (0.39735^e235) + (0.31698^e245) - (0.63557^e345),rgb(255,0,0));
DrawCircle((0.01985^e123) - (2.05838^e124) - (2.09249^e125) + (2.64657^e134) + (2.68935^e135) + (0.11261^e145) - (0.58045^e234) - (0.59451^e235) + (0.46053^e245) - (0.62388^e345),rgb(255,0,0));
DrawCircle((0.11265^e123) - (1.91934^e124) - (1.94452^e125) + (4.36334^e134) + (4.41186^e135) + (0.14899^e145) + (0.17264^e234) + (0.15837^e235) + (0.2816^e245) - (0.62677^e345),rgb(255,0,0));
DrawCircle((0.15172^e123) - (2.14627^e124) - (2.1724^e125) + (4.13471^e134) + (4.18365^e135) + (0.01957^e145) + (1.08776^e234) + (1.0771^e235) + (0.33811^e245) - (0.64143^e345),rgb(255,0,0));
DrawCircle((0.21206^e123) - (1.26215^e124) - (1.29761^e125) + (3.34958^e134) + (3.39347^e135) + (0.29888^e145) + (2.70183^e234) + (2.69901^e235) + (0.4686^e245) - (0.6038^e345),rgb(255,0,0));
DrawCircle((0.19919^e123) - (0.04541^e124) - (0.06615^e125) + (3.80112^e134) + (3.85319^e135) + (0.38392^e145) + (2.11193^e234) + (2.10485^e235) + (0.22152^e245) - (0.68714^e345),rgb(255,0,0));
DrawCircle((0.07493^e123) - (1.80694^e124) - (1.8392^e125) + (2.82433^e134) + (2.8679^e135) + (0.16525^e145) + (0.10182^e234) + (0.08592^e235) + (0.42708^e245) - (0.65822^e345),rgb(255,0,0));
DrawCircle((0.0579^e123) - (1.17628^e124) - (1.1965^e125) + (3.15052^e134) + (3.1985^e135) + (0.1255^e145) - (0.54845^e234) - (0.57038^e235) + (0.25402^e245) - (0.73888^e345),rgb(255,0,0));
DrawCircle((0.15943^e123) - (1.09309^e124) - (1.11996^e125) + (3.59027^e134) + (3.63993^e135) + (0.26474^e145) + (1.97432^e234) + (1.97268^e235) + (0.34403^e245) - (0.65181^e345),rgb(255,0,0));
DrawCircle((0.10352^e123) - (1.38953^e124) - (1.42221^e125) + (3.15972^e134) + (3.20447^e135) + (0.39671^e145) + (0.62817^e234) + (0.61712^e235) + (0.34651^e245) - (0.6086^e345),rgb(255,0,0));

This cluster generation function appears in clifford tools by default and it can be imported as follows:

[4]:

from clifford.tools.g3c import generate_random_object_cluster

Now that we can generate individual clusters we would like to generate many:

[5]:

def generate_n_clusters( object_generator, n_clusters, n_objects_per_cluster ):
    object_clusters = []
    for i in range(n_clusters):
        cluster_objects = generate_random_object_cluster(n_objects_per_cluster, object_generator,
                                                         max_cluster_trans=0.5, max_cluster_rot=np.pi / 16)
        object_clusters.append(cluster_objects)
    all_objects = [item for sublist in object_clusters for item in sublist]
    return all_objects, object_clusters

Again this function appears by default in clifford tools and we can easily visualise the result:

[6]:

from clifford.tools.g3c import generate_n_clusters

all_objects, object_clusters = generate_n_clusters(random_circle, 2, 5)
sc = GAScene()
for c in all_objects:
    sc.add_circle(c,'rgb(255,0,0)')
print(sc)

DrawCircle((0.87666^e123) + (7.54167^e124) + (7.59841^e125) - (0.61464^e134) - (0.66444^e135) - (0.38863^e145) - (10.425^e234) - (10.40965^e235) + (0.80686^e245) - (0.60297^e345),rgb(255,0,0));
DrawCircle((0.91225^e123) + (7.08106^e124) + (7.13537^e125) - (4.43487^e134) - (4.48627^e135) - (0.13496^e145) - (9.83868^e234) - (9.82015^e235) + (0.72965^e245) - (0.6445^e345),rgb(255,0,0));
DrawCircle((0.8988^e123) + (7.66328^e124) + (7.72836^e125) - (2.00536^e134) - (2.0423^e135) - (0.16972^e145) - (10.11453^e234) - (10.09622^e235) + (0.88857^e245) - (0.45653^e345),rgb(255,0,0));
DrawCircle((0.8953^e123) + (7.12706^e124) + (7.18912^e125) - (2.08383^e134) - (2.12483^e135) - (0.18193^e145) - (10.96343^e234) - (10.94336^e235) + (0.91976^e245) - (0.54878^e345),rgb(255,0,0));
DrawCircle((0.8623^e123) + (7.20179^e124) + (7.26338^e125) - (0.93297^e134) - (0.9769^e135) - (0.30028^e145) - (9.96474^e234) - (9.95018^e235) + (0.83334^e245) - (0.52344^e345),rgb(255,0,0));
DrawCircle((0.08044^e123) - (1.11059^e124) - (1.14625^e125) - (0.26643^e134) - (0.32992^e135) + (0.75837^e145) - (0.42648^e234) - (0.47554^e235) + (0.4883^e245) - (0.17408^e345),rgb(255,0,0));
DrawCircle((0.09868^e123) - (1.33622^e124) - (1.36988^e125) - (0.2825^e134) - (0.33829^e135) + (0.65912^e145) - (0.67328^e234) - (0.73213^e235) + (0.56732^e245) - (0.21217^e345),rgb(255,0,0));
DrawCircle((0.15805^e123) - (1.89186^e124) - (1.92636^e125) + (0.00294^e134) - (0.05364^e135) + (0.67791^e145) - (0.45991^e234) - (0.51751^e235) + (0.58912^e245) - (0.16571^e345),rgb(255,0,0));
DrawCircle((0.10434^e123) - (1.40477^e124) - (1.43961^e125) - (0.31972^e134) - (0.38036^e135) + (0.70966^e145) - (0.59998^e234) - (0.65306^e235) + (0.51438^e245) - (0.18603^e345),rgb(255,0,0));
DrawCircle((0.11818^e123) - (1.45613^e124) - (1.48421^e125) - (0.23195^e134) - (0.2923^e135) + (0.68855^e145) - (0.57788^e234) - (0.63513^e235) + (0.56815^e245) - (0.18276^e345),rgb(255,0,0));

Given that we can now generate multiple clusters of objects we can test algorithms for segmenting them.

The function run_n_clusters below generates a lot of objects distributed into n clusters and then attempts to segment the objects to recover the clusters.

[7]:

from clifford.tools.g3c.object_clustering import n_clusters_objects
import time

def run_n_clusters( object_generator, n_clusters, n_objects_per_cluster, n_shotgunning):
    all_objects, object_clusters = generate_n_clusters( object_generator, n_clusters, n_objects_per_cluster )
    [new_labels, centroids, start_labels, start_centroids] = n_clusters_objects(n_clusters, all_objects,
                                                                                initial_centroids=None,
                                                                                n_shotgunning=n_shotgunning,
                                                                                averaging_method='unweighted')
    return all_objects, new_labels, centroids

Lets try it!

[8]:

from clifford.tools.g3c.object_clustering import visualise_n_clusters

object_generator = random_circle

n_clusters = 3
n_objects_per_cluster = 10
n_shotgunning = 60
all_objects, labels, centroids = run_n_clusters(object_generator, n_clusters,
                                                     n_objects_per_cluster, n_shotgunning)

sc = visualise_n_clusters(all_objects, centroids, labels, object_type='circle',
                     color_1=np.array([255, 0, 0]), color_2=np.array([0, 255, 0]))
print(sc)

DrawCircle((0.68485^e123) + (6.24902^e124) + (6.30374^e125) - (6.31041^e134) - (6.33261^e135) + (0.30165^e145) - (2.55126^e234) - (2.59795^e235) - (0.22208^e245) + (0.34742^e345),rgb(255, 0, 0));
DrawCircle((0.64711^e123) + (7.14408^e124) + (7.20519^e125) - (4.54276^e134) - (4.55424^e135) + (0.30227^e145) - (2.88929^e234) - (2.93172^e235) - (0.19553^e245) + (0.24658^e345),rgb(255, 0, 0));
DrawCircle((0.63275^e123) + (6.11699^e124) + (6.17034^e125) - (5.28134^e134) - (5.30106^e135) + (0.25469^e145) - (3.48347^e234) - (3.53278^e235) - (0.18298^e245) + (0.30303^e345),rgb(255, 0, 0));
DrawCircle((0.64396^e123) + (5.41253^e124) + (5.46651^e125) - (6.20851^e134) - (6.23341^e135) + (0.31115^e145) - (3.31053^e234) - (3.35672^e235) - (0.11067^e245) + (0.31725^e345),rgb(255, 0, 0));
DrawCircle((0.64554^e123) + (6.34967^e124) + (6.40425^e125) - (5.02826^e134) - (5.04445^e135) + (0.26592^e145) - (3.80677^e234) - (3.85601^e235) - (0.16245^e245) + (0.28807^e345),rgb(255, 0, 0));
DrawCircle((0.63623^e123) + (6.02215^e124) + (6.07584^e125) - (5.66496^e134) - (5.68868^e135) + (0.25353^e145) - (3.11678^e234) - (3.16391^e235) - (0.18314^e245) + (0.30349^e345),rgb(255, 0, 0));
DrawCircle((0.55306^e123) + (5.5761^e124) + (5.62997^e125) - (4.4988^e134) - (4.51091^e135) + (0.31603^e145) - (3.23283^e234) - (3.284^e235) - (0.20108^e245) + (0.34546^e345),rgb(255, 0, 0));
DrawCircle((0.61675^e123) + (5.60958^e124) + (5.65927^e125) - (5.54058^e134) - (5.56192^e135) + (0.25236^e145) - (3.30627^e234) - (3.35864^e235) - (0.2099^e245) + (0.35605^e345),rgb(255, 0, 0));
DrawCircle((0.66315^e123) + (6.0908^e124) + (6.1442^e125) - (5.52148^e134) - (5.54104^e135) + (0.26492^e145) - (4.00098^e234) - (4.05029^e235) - (0.13077^e245) + (0.29257^e345),rgb(255, 0, 0));
DrawCircle((0.61874^e123) + (5.6324^e124) + (5.68181^e125) - (5.225^e134) - (5.24559^e135) + (0.22987^e145) - (4.07242^e234) - (4.12534^e235) - (0.15648^e245) + (0.31137^e345),rgb(255, 0, 0));
DrawCircle((0.15424^e123) - (2.43729^e124) - (2.44397^e125) + (2.01493^e134) + (1.97097^e135) + (0.78195^e145) - (3.42214^e234) - (3.38023^e235) - (0.81058^e245) - (0.4278^e345),rgb(0, 255, 0));
DrawCircle((0.1396^e123) - (2.30571^e124) - (2.3068^e125) + (2.01853^e134) + (1.9696^e135) + (0.82387^e145) - (3.24641^e234) - (3.20983^e235) - (0.62957^e245) - (0.60884^e345),rgb(0, 255, 0));
DrawCircle((0.15401^e123) - (2.81545^e124) - (2.81566^e125) + (2.47646^e134) + (2.42443^e135) + (0.95462^e145) - (2.84849^e234) - (2.81644^e235) - (0.58979^e245) - (0.44704^e345),rgb(0, 255, 0));
DrawCircle((0.20691^e123) - (3.24488^e124) - (3.25449^e125) + (2.09334^e134) + (2.04213^e135) + (0.90035^e145) - (2.93203^e234) - (2.90011^e235) - (0.63674^e245) - (0.40277^e345),rgb(0, 255, 0));
DrawCircle((0.12181^e123) - (2.21468^e124) - (2.21598^e125) + (2.62546^e134) + (2.5753^e135) + (0.93993^e145) - (2.71922^e234) - (2.68435^e235) - (0.66268^e245) - (0.36847^e345),rgb(0, 255, 0));
DrawCircle((0.149^e123) - (2.62272^e124) - (2.6222^e125) + (1.67148^e134) + (1.62418^e135) + (0.82683^e145) - (3.03762^e234) - (2.99895^e235) - (0.67024^e245) - (0.53048^e345),rgb(0, 255, 0));
DrawCircle((0.17783^e123) - (2.61601^e124) - (2.62735^e125) + (2.16106^e134) + (2.11308^e135) + (0.84381^e145) - (3.09308^e234) - (3.057^e235) - (0.72817^e245) - (0.39615^e345),rgb(0, 255, 0));
DrawCircle((0.12659^e123) - (1.94155^e124) - (1.94891^e125) + (2.13081^e134) + (2.08271^e135) + (0.86165^e145) - (2.56095^e234) - (2.52399^e235) - (0.71579^e245) - (0.35097^e345),rgb(0, 255, 0));
DrawCircle((0.17823^e123) - (2.97963^e124) - (2.98573^e125) + (1.82884^e134) + (1.78111^e135) + (0.86048^e145) - (2.66558^e234) - (2.62792^e235) - (0.72073^e245) - (0.32742^e345),rgb(0, 255, 0));
DrawCircle((0.12041^e123) - (1.91178^e124) - (1.91609^e125) + (2.1151^e134) + (2.07165^e135) + (0.76557^e145) - (3.44785^e234) - (3.4051^e235) - (0.80222^e245) - (0.49315^e345),rgb(0, 255, 0));
DrawCircle(-(0.942^e123) - (6.36368^e124) - (6.29933^e125) - (7.8045^e134) - (7.80066^e135) - (0.50717^e145) + (11.5101^e234) + (11.55736^e235) + (1.10563^e245) + (0.43863^e345),rgb(127, 127, 0));
DrawCircle(-(1.01185^e123) - (8.39026^e124) - (8.337^e125) - (7.53917^e134) - (7.5249^e135) - (0.27847^e145) + (12.25339^e234) + (12.31127^e235) + (1.12489^e245) + (0.6041^e345),rgb(127, 127, 0));
DrawCircle(-(1.0489^e123) - (8.10852^e124) - (8.04853^e125) - (7.54005^e134) - (7.53862^e135) - (0.42023^e145) + (13.22555^e234) + (13.27837^e235) + (1.16472^e245) + (0.39764^e345),rgb(127, 127, 0));
DrawCircle(-(0.98846^e123) - (5.60724^e124) - (5.54657^e125) - (6.64749^e134) - (6.63981^e135) - (0.36445^e145) + (12.56074^e234) + (12.61222^e235) + (1.06301^e245) + (0.44381^e345),rgb(127, 127, 0));
DrawCircle(-(1.01155^e123) - (8.0402^e124) - (7.98128^e125) - (7.88063^e134) - (7.87324^e135) - (0.40028^e145) + (12.47477^e234) + (12.52829^e235) + (1.152^e245) + (0.50808^e345),rgb(127, 127, 0));
DrawCircle(-(1.02813^e123) - (5.89861^e124) - (5.83245^e125) - (6.37472^e134) - (6.37136^e135) - (0.39094^e145) + (14.0985^e234) + (14.14325^e235) + (1.16392^e245) + (0.32347^e345),rgb(127, 127, 0));
DrawCircle(-(0.96446^e123) - (5.35708^e124) - (5.29251^e125) - (7.45428^e134) - (7.44595^e135) - (0.45284^e145) + (12.33638^e234) + (12.38276^e235) + (1.08359^e245) + (0.46498^e345),rgb(127, 127, 0));
DrawCircle(-(1.06315^e123) - (6.09028^e124) - (6.02794^e125) - (7.69743^e134) - (7.69279^e135) - (0.42484^e145) + (13.90322^e234) + (13.95304^e235) + (1.10071^e245) + (0.42133^e345),rgb(127, 127, 0));
DrawCircle(-(0.97763^e123) - (5.94717^e124) - (5.88806^e125) - (8.86402^e134) - (8.85236^e135) - (0.4651^e145) + (11.61567^e234) + (11.6682^e235) + (1.02197^e245) + (0.61479^e345),rgb(127, 127, 0));
DrawCircle(-(0.95905^e123) - (4.29184^e124) - (4.22574^e125) - (6.36413^e134) - (6.35183^e135) - (0.38357^e145) + (12.89096^e234) + (12.93421^e235) + (1.08196^e245) + (0.4523^e345),rgb(127, 127, 0));
DrawCircle((0.15384^e123) - (2.52703^e124) - (2.53174^e125) + (2.13016^e134) + (2.08164^e135) + (0.86223^e145) - (3.01442^e234) - (2.97737^e235) - (0.70078^e245) - (0.43781^e345),rgb(0,0,0));
DrawCircle(-(1.00184^e123) - (6.53393^e124) - (6.47166^e125) - (7.46069^e134) - (7.45305^e135) - (0.41385^e145) + (12.76209^e234) + (12.81217^e235) + (1.11984^e245) + (0.47033^e345),rgb(0,0,0));
DrawCircle((0.63737^e123) + (6.04874^e124) + (6.10283^e125) - (5.41425^e134) - (5.43349^e135) + (0.2769^e145) - (3.39452^e234) - (3.44344^e235) - (0.17617^e245) + (0.31309^e345),rgb(0,0,0));